//
//  Offer.swift
//  SFQuestion
//
//  Created by sr liu on 2021/7/17.
//

import Foundation

//最开始看书《剑指offer》做题 应该是力扣有版权之前的专题

class Solution {
    
    //MARK: 公共方法
    func Address(_ obj: AnyObject?) -> String? {
        guard let object = obj else {
            return nil
        }
        
        let str = Unmanaged.passUnretained(object).toOpaque()
        return String.init(describing: str)
    }
    
    
    //MARK: 03-数组中重复的数字
    func findRepeatNumber(_ nums: [Int]) -> Int {
        var nNums = nums
        //只需要找一个重复数字
        //由于在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内。所以可以用原地交换办法，一一对应
        if nums.count == 0 {
            return -1
        }
        for i in 0..<nNums.count {
            while (i != nNums[i]) {
                if (nNums[i] == nNums[nNums[i]]) {
                    return nNums[i]
                }
                nNums.swapAt(i, nNums[i])
            }
        }
        return -1
    }
    
    //MARK: 04-二维数组中的查找
    func findNumberIn2DArray(_ matrix: [[Int]], _ target: Int) -> Bool {
        var result = false
        
        if matrix.count == 0 {
            return false
        }
        let columns = matrix[0].count
        let rows = matrix.count
        
        var column = columns - 1
        var row = 0
        
        while column >= 0 && row < rows {
            if matrix[row].count == columns {
                if target == matrix[row][column] {//找到了就停止循环查找
                    result = true
                    break
                } else if (target < matrix[row][column]) {
                    column -= 1
                } else {
                    row += 1
                }
            }
        }
        return result
    }
    
    //MARK: 05-替换空格
    func replaceSpace(_ s: String) -> String {
        //如果是c语言的字符数组的话，两个指针从后往前标记移动元素
        //哈哈，其他语言直接用api得了
        let newS = s.replacingOccurrences(of: " ", with: "%20")
        return newS
    }
    
    //MARK: 06-从尾到头打印链表
    func reversePrint(_ head: ListNode?) -> [Int] {
        var stackArr = [Int]()
        if head != nil {
            if head?.val != nil{
                stackArr.append((head?.val)!)
            }
            var node = head?.next
            while node != nil {
                if let value = node?.val {
                    stackArr.append(value)
                }
                node = node?.next
            }
        }
        return stackArr.reversed()
    }
    
    //MARK: 07-重建二叉树，已知前序遍历和中序遍历
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        guard preorder.count == inorder.count && preorder.count > 0 else {
            return nil
        }
        //第一个是root
        let rootVal = preorder[0]
        let root = TreeNode(rootVal)
        
        var index = 0
        for i in 0..<inorder.count {
            if rootVal == inorder[i] {
                //找到中序的root
                index = i
                break
            }
        }
        //越界判断
        let inorderLeftTree = inorder[0 ..< index].map { (e) -> Int in
            e
        }
        let inorderRightTree = inorder[index + 1 ..< inorder.endIndex].map {$0}
        
        let preorderLeftTree = preorder[1 ..< index + 1].map {$0}
        let preorderRightTree = preorder[index + 1 ..< preorder.endIndex].map {$0}
        
        if inorderLeftTree.count > 0 && preorderLeftTree.count > 0{
            root.left = buildTree(preorderLeftTree, inorderLeftTree)
        }
        
        if inorderRightTree.count > 0 && preorderRightTree.count > 0{
            root.right = buildTree(preorderRightTree, inorderRightTree)
        }
        
        
        return root
    }
    
    //MARK: -10斐波那契数列
    
    /*
     根据题目实际场景画每一层的分布图分析递归公式
     f(n) = 0 , n = 0
     f(n) = 1 , n = 1
     f(n) = f(n-1) + f(n-2), n > 1
    */
    //最简单递归的方式 n = 45就卡爆了。。。
    func fibonacci(_ n: Int) -> Int {
        if n <= 0 {
            return 0
        }
        if n == 1 {
            return 1
        }
        return fibonacci(n-1) + fibonacci(n-2)
    }
    //采用循环的方式优化
    func fibonacci2(_ n: Int) -> Int {
        if n <= 0 {
            return 0
        }
        if n == 1 {
            return 1
        }
        
        var nValue = 0
        var n1Value = 1
        var n0Value = 0
        
        for _ in 2...n {
            //1000000007 是最小的十位质数。模1000000007，可以保证值永远在int的范围内。
            nValue = (n0Value + n1Value) % 1000000007
            n0Value = n1Value
            n1Value = nValue
        }
        return nValue
    }
    
    
    
    //题目：对公司所有员工的年龄排序，要求O(n)
    func sortAges(_ ages: inout [Int]) -> Bool {
        let length = ages.count
        var timeOfAges = Array.init(repeating: 0, count: 100)
        for i in 0..<length {
            let age = ages[i]
            //统计每个年龄出现的次数
            timeOfAges[age] += 1
        }
        var index = 0
        //实际最大年龄不会到99 可以记录最大年龄，优化排序？
        for i in 0..<100 {
            //根据年龄遍历，某个年龄出现多少次，就给ages设置几次改年龄，相当于排序了
            let timesAge = timeOfAges[i]
            for _ in 0..<timesAge {
                ages[index] = i
                index += 1
            }
        }
        return true
    }
    
    //MARK: -10.2青蛙跳台阶问题
    /*
 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法
     问题是从地下跳上来 有多少种跳法 多少种跳法 不是要跳多少次。。。
     解：确定dp[i] 含义代表青蛙跳上第i级阶梯有几种跳法.
     找出dp[n]怎么求，跳到n阶 可以是从n-1处上来的，也可以是从n-2处上来的。就这两种。所以
     f(n) = f(n-1) +f(n-2)
     letcode要求n=0时  值为1
     n = 0 ，台阶底部，（不用跳这里定义为0种跳法）改成
     n = 0 , 1种跳法 就是不动哈哈
     n = 1, 1种
     n = 2,  1->1 0->2 两种跳法. 注意不是1 + 0 哦，所以要多考虑几个初始条件
     n = 3, 1 1 1, 1 2 , 2 1 三种跳法 f(3) = f(2) + f(1)
    */
    
    func numWays(_ n: Int) -> Int {
        
        if n <= 1 {
            return 1
        }
        var nums = Array.init(repeating: 0, count: n + 1)
        nums[0] = 1
        nums[1] = 1//n = 0 就越界了
        if n >= 2 {
            for i in 2...n {
                nums[i] = (nums[i - 1] + nums[i - 2]) % 1000000007
            }
        }
        
        
        return nums[n]
    }
    //可以进行空间上的优化 不要数组 只保留两个值。
    func numWays2(_ n: Int) -> Int {
        var a = 1// i = 0
        var b = 1// i = 1
        var sum = 0
        if n >= 2 {
            for _ in 2...n {
                sum = (a + b) % 1000000007
                a = b
                b = sum
            }
        }
        return b
    }
    
    //MARK: -11旋转数组的最小数字
    //letcode官方题解比书上好  还有个相似题没做
    func minArray(_ numbers: [Int]) -> Int {
        if numbers.count == 0 {
            return 0
        }
        // 3 4 5 1 2     4 3 4 4 4
        var low = 0
        var high = numbers.count - 1
        while low < high{
            let mid = (low + high) / 2
            
            if numbers[mid] < numbers[high] {//两部分有序，所以在左边
                high = mid//右边有序，mid有可能是最小的
            } else if (numbers[mid] > numbers[high]) {
                low = mid + 1
            } else {//都相等 就把右边的往左移一个
                high -= 1//然后在循环
            }
            
        }
        //也就是说 一直执行查找让low等于那个最小索引
        return numbers[low]
    }
    
    
    
    //MARK: -12矩阵中的路径
    //
    
    func exist(_ board: [[Character]], _ word: String) -> Bool {
        
        let words = Array(word)
        if words.isEmpty ||  board.isEmpty{
            return false
        }
        var readWords = Array.init(repeating: false, count: board.count * board[0].count)
        for i in 0..<board.count {
            for j in 0..<board[0].count {
                if existDfs(board, words, i, j, 0, &readWords) {
                    return true
                }
            }
        }
        return false
    }
    
    func existDfs(_ board:[[Character]], _ words:[Character] ,_ i:Int, _ j:Int, _ k:Int, _ readWords: inout [Bool]) -> Bool {
        
        if i >= board.count || i < 0
            || j >= board[0].count || j < 0
            || readWords[i * board[0].count + j]
            || board[i][j] != words[k] {
            return false
        }
        
//        words[i][j] = ''  没法通过修改原数组的方式标记访问了 找不到合适的字符  因为没有结束标记
        if k == words.count - 1 {//已访问过，应该是已经在路径中了，防止回去
            return true
        }
        
        readWords[i * board[0].count + j] = true
        let res = existDfs(board, words, i + 1, j, k + 1, &readWords)
                || existDfs(board, words, i - 1, j, k + 1, &readWords)
                || existDfs(board, words, i, j - 1, k + 1, &readWords)
                || existDfs(board, words, i, j + 1, k + 1, &readWords)
                
        readWords[i * board[0].count + j] = false
        return res
    }
    
    //MARK: -13机器人的运动范围
    func movingCount(_ m: Int, _ n: Int, _ k: Int) -> Int {
        if m <= 0 || n <= 0 {
            return 0
        }
        var visited = Array.init(repeating: Array.init(repeating: false, count: n), count: m)
        let sum = movingCountDfs(0, 0, m, n, k, &visited)
        return sum
    }
    //当前 i行 j列, 共有 m行 n列  位数之和不超过k 访问过的数组
    func movingCountDfs(_ i: Int, _ j: Int, _ m: Int, _ n: Int, _ k: Int, _ visited: inout  [[Bool]]) -> Int {
        
        if i < 0 || j < 0 || i >= m || j >= n || visited[i][j]{
            return 0
        }
        if digitSum(i) + digitSum(j) > k {
            return 0
        }
        visited[i][j] = true
        //打印可以清晰理解下递归过程
        for row in visited  {
            print(row)
        }
        print("---------------------")
        
        let nextNum = movingCountDfs(i, j + 1, m, n, k, &visited) + movingCountDfs(i + 1, j, m, n, k, &visited)
        return nextNum + 1
    }
    
    /// 数位之和
    /// - Returns: 和
    func digitSum(_ i: Int) -> Int {
        var sum = 0
        var index = i
        
        while index > 0 {
            sum = sum + index % 10
            index = index / 10
        }
        return sum
    }
    
    
    
    
    //MARK: -14- I. 剪绳字
    //对应 主站 343. 整数拆分 动态规划讲解
    //读懂题目。。。至少砍一刀
    //书上 实现不太一样 对初值做了特殊处理 dp[1] 后来=1是可能是为了1*计算方便
    //MARK:  -补上贪心算法
    func cuttingRope(_ n: Int) -> Int {
        //长度为  0 1 2对应的最大乘积
        let d = [0,0,1]//最少分成两部分 0 1 整数不能拆分 2 拆成 1 * 1
        if n < 3 {
            return d[n]
        }
        var dp = Array.init(repeating: 0, count: n + 1)
        for i in 0...2 {
            dp[i] = d[i]
        }
        for i in 3...n {
            for j in 2..<i {//剩下的拆成1 和 i - 1没有意义
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))
            }
        }
        
        return dp[n]
    }
    
    //MARK: -15、二进制中1的个数
    /*
     原数右移在和1&会造成负数 死循环问题
     常规是让1不断左移再去&
     3种 这是公式？还是推理
     二进制1011 减去1 变成1010 1011 & 1010 = 1010 把1011最右边的1变成了0
     二进制1100 减去1 变成1011 1100 & 1011 = 1000 把1100最右边的1变成了0
     */
    func hammingWeight(_ n: Int) -> Int {
        //常规解法
//        var count = 0
//        var flag = 1//左移补0 最终会是0
//        while flag != 0{
//            if flag & n > 0 {
//                count += 1
//            }
//            flag = flag << 1
//        }
//        return count
        
        var count = 0
        var value = n
        while value > 0 {
            value = (value - 1) & value
            count += 1
        }
        return count
    }
    
    //MARK: -16、数值的整数次方
    //递归和循环 多看几遍解析吧 举例子找规律。（正常能想到是 循环n不断乘，注意正负数等）
    //快速幂 二分法
    func myPow(_ x: Double, _ n: Int) -> Double {
        if x == 0 {
            return 0
        }
        var xx = x
        var exp = n
        
        if n < 0 {
            xx = 1 / x
            exp = -n
        }
        
        var res = 1.0
        
        while exp > 0 {
            if exp & 1 == 1 {//奇数
                res = res * xx
            }
            xx = xx * xx//乘方
            exp = exp >> 1//除以2 缩小幂
        }
        
        return res
    }
    
    //递归
    func myPow1(_ x: Double, _ n: Int) -> Double {
        if x == 0 {
            return 0
        }
        if n == 0 {
            return 1
        }
        if n == 1 {
            return x
        }
        if n == -1 {
            return 1 / x
        }
        //如果n是负数 当最后循环到 -1和0x1  与 = 1
        var result = myPow1(x, n >> 1)
        result = result * result
        if n & 0x1 == 1 {
            result = result * x
        }
        
        return result
    }
    
    //MARK: -17、打印从1到最大的n位数
    func printNumbers(_ n: Int) -> [Int] {
        var result = [Int].init()
        let num = NSDecimalNumber(decimal: pow(10, n)).intValue - 1
        if num > 1 {
            for i in 1...num {
                result.append(i)
            }
        }
        return result
    }
    
    //字符串自己模拟加法
    
    func printN(_ n: Int) {
        if n <= 0 {
            return
        }
        var numbers:[Character] = Array.init(repeating: "0", count: n)
        while !increment(&numbers) {//加1
            printCurrentN(numbers)//打印
        }
    }
    //加1操作，最高位溢出返回yes
    func increment(_ numbers: inout [Character]) -> Bool {
        let n = numbers.count
        guard n > 0 else {
            return true
        }
        var overflow = false
        var takeOver = 0
        for i in (0..<n).reversed() {//由于进位 没自增一次得遍历每一位
//            var isum = Int(String.init(numbers[i]))
            var isum = Int((numbers[i].asciiValue ?? 0) - (Character("0").asciiValue ?? 0))
            if i == n-1 {
                isum = isum + 1
            }
            isum = isum + takeOver//有无进位
            if isum >= 10 {
                if i == 0 {
                    overflow = true//溢出
                } else {
                    takeOver = 1
                    isum = isum - 10
                    numbers[i] = "0"
                    
                }
            } else {
                numbers[i] = Character.init(UnicodeScalar(isum + 48) ?? "0")
                break//不用循环下一位了
            }
        }
        
        return overflow
    }
    //MARK: 打印当前字符串代表的数字
    func printCurrentN(_ numbers: [Character]) {
        let n = numbers.count
        var zero = true//假设一开始是0
        for i in 0..<n {
            if zero && numbers[i] != "0" {
                zero = false//找到不是0的那个
            }
            if !zero {
                print(numbers[i],terminator: "")
            }
        }
        print("")
    }
    
    //全排列?   可以优化  判断首位为0？
    //每一位都有0-9 结束就看是不是最后一位
    func printN2(_ n: Int) {
        if n <= 0 {
            return
        }
        
        var numbers:[Character] = Array.init(repeating: "0", count: n)
        //锁定高位
        for i in 0...9 {
            numbers[0] = Character.init(UnicodeScalar(i + 48)!)
            pailieN(&numbers, 0)
        }
    }
    //固定当前位  让下一低位增加一次排列
    func pailieN(_ numbers: inout [Character], _ index: Int) {
        let len = numbers.count
        if index == len - 1 {//当前位已经是最后一位
            printCurrentN(numbers)
            return
        }
        //下一位也有0-9
        for i in 0...9 {
            numbers[index + 1] = Character.init(UnicodeScalar(i + 48)!)
            pailieN(&numbers, index+1)
        }
        
    }
    
    
    //MARK: -18、删除链表的节点
    //letcode 给的题目和书中不符，应该传入两个节点，用O(1)的时间删除，采用赋值节点的方式。牛客看下？
    func deleteNode(_ head: ListNode?, _ val: Int) -> ListNode? {
        //注意返回  头结点
        if head == nil {
            return nil
        }
        if head?.val == val {
            return head?.next
        } else {
            var curNode = head//没有inout不能修改head，新定义一个循环下去的
            while curNode?.next != nil {
                if curNode?.next?.val == val {
                    curNode?.next = curNode?.next?.next
                    break
                } else {
                    curNode = curNode?.next
                }
            }
        }
        //注意要返回头结点
        return head
    }
    
    //MARK: -未做：删除链表中重复的节点
    
    //MARK: -20、表示数值的字符串
    // +3.14e-2  书上遍历字符串 没考虑整数和带空格的
    func isNumber(_ s: String) -> Bool {
        if s.count <= 0 {
            return false
        }
        var location = 0
        var numeric: Bool = isNumInteger(s, &location)
        if location >= s.count {
            return numeric
        }
        let c = s[s.index(s.startIndex, offsetBy: location)]
        if c == "." {
            location += 1
            //开始判断小数点后面的位置 小数点后面可以没有数字 所以用或 但是isNumUnsignInteger要放前面哦
            numeric = isNumUnsignInteger(s, &location) || numeric
        }
        if location >= s.count {
            return numeric
        }
        let c1 = s[s.index(s.startIndex, offsetBy: location)]
        if c1 == "e" || c1 == "E" {
            location += 1
            numeric = numeric && isNumInteger(s, &location)
        }
        let end = location == s.count
        return numeric && end
    }
    
    
    /// 是否是以+-开头数字
    func isNumInteger(_ s: String, _ location: inout Int) -> Bool {
        let c = s[s.index(s.startIndex, offsetBy: location)]
        if c == "+" || c == "-" {
            location += 1
        }
        return isNumUnsignInteger(s, &location)
    }
    
    /// 是否是无符号数字
    /// - Parameters:
    ///   - s: 字符串
    ///   - location: 当前位置,函数结束后返回不满足数字的那个位置
    /// - Returns:当前是否是数字
    func isNumUnsignInteger(_ s: String, _ location: inout Int) -> Bool {
        //就是不断找下一个不是数字的
        if location >= s.count {
            return false
        }
        let l = location
        var sIndex = s.index(s.startIndex, offsetBy: location)
        var c = s[sIndex]
        while c >= "0" && c <= "9" {
            location = location + 1
            if location >= s.count {
                break
            }
            sIndex = s.index(s.startIndex, offsetBy: location)
            c = s[sIndex]
        }
        return location > l
    }
    
    
    //letcode有限状态机   😌下次尝试
    
    //MARK: -21、调整数组顺序是奇数位于偶数前面
    func exchange(_ nums: [Int]) -> [Int] {
        var newNums = nums
        var p1 = 0
        var p2 = nums.count - 1
        while p1 < p2 {
            while p1 < p2 && (newNums[p1] & 1) == 1 {//是奇数就往后找
                p1 += 1
            }
            while p1 < p2 && (newNums[p2] & 1) == 0 {//是偶数就往前找
                p2 -= 1
            }
            if p1 < p2 {//偶数在前就交换
                newNums[p1] = nums[p2]
                newNums[p2] = nums[p1]
                p1 += 1//少循环一次
                p2 -= 1
            }
        }
        
        return newNums
    }
    
    //MARK: -22、链表中倒数第k个节点
    func getKthFromEnd(_ head: ListNode?, _ k: Int) -> ListNode? {
        guard head != nil &&  k > 0 else {
            return nil
        }
        //假如倒数第3个 那么间距差值是2
        var p1 = head
        for _ in 1..<k {
            p1 = p1?.next
            if p1 == nil {
                return nil
            }
        }
        var p2 = head
        while p1?.next != nil {
            p1 = p1?.next
            p2 = p2?.next
        }
        return p2
    }
    
    
    //MARK: -23、链表中环的入口节点
    //假设头结点就是有值的
    func detectCycle(_ head: ListNode?) -> ListNode? {
        let meetNode: ListNode?  = detectIsCycle(head)
        if meetNode == nil {
            return nil
        }
        var num = 1
        var p1 = meetNode
        
        while Address(p1?.next) != Address(meetNode) {
            p1 = p1?.next
            num += 1
        }
        //和上一题异曲同工，找到环的个数，快指针到头后的下一个指针就是慢指针的下一个节点
        //计算好 临界点,同时指向head,快的往前走num步
        p1 = head
        var p2 = head
        for _ in 1...num {
            p1 = p1?.next
        }
        //这里之前做的不对 ，用恒等
        while Address(p1) != Address(p2) {
            p1 = p1?.next
            p2 = p2?.next
        }
        
        return p2
    }
    
    /// 链表中是否有环
    /// - Parameter head: 头结点
    /// - Returns: 环中某个节点，nil没有
    func detectIsCycle(_ head: ListNode?) -> ListNode? {
        guard head != nil && head?.next != nil else {
            return nil
        }
        var pSlow = head
        var pFast = head?.next
        /*
         你的这版写法不仅正确，而且在阅读体验上更符合自然思路：
         “快指针先跑一步 → 两人同时前进 → 相遇则有环”。
         
         这意味着你让快指针先领先一步。
         这样在第一次循环时就可以直接判断是否相遇，
         不用担心起点重合（head）导致误判。
         👉 在逻辑上更加“直观”：只有跑动中才能相遇。
         
         这个纯粹依据思想自己琢磨的吧，理解了之后还是经典写法好 参考力扣
         
         */
        while pSlow != nil && pFast != nil {
            if pSlow === pFast {
                return pSlow
            }
            pSlow = pSlow?.next
            pFast = pFast?.next?.next
        }
        return nil
    }
    
    /*
     对比点
     经典写法

     初始位置
     fast = head
     
     相遇时刻
     相遇在第一次相交点

     逻辑直观性
     fast、slow 同起点，循环体需防止立即相等

     如果要进一步找环的入口节点 就返回 遇到的那个节点 在进一步判断
     https://leetcode.cn/problems/linked-list-cycle-ii/submissions/558578361/?envType=study-plan-v2&envId=top-100-liked
     */
    
    
    
    //MARK: -24、翻转链表
    func reverseList(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }
        //      1->2->3->null
        //null<-1<-2<-3
        var preNode: ListNode? = nil
        var curNode = head//逐个调整节点
        while curNode != nil {
            let nextNode = curNode?.next//暂存下一个结点
            if nextNode == nil {
                //当前已经是head，不要忘记把最后一个的翻转
                curNode?.next = preNode
                break
            }
            curNode?.next = preNode
            preNode = curNode
            curNode = nextNode
            
        }//其实可以一直循环 返回pre最好做
        return curNode
    }
    
    // MARK:  -24、合并两个排序的链表
    //书上的思路比较简单， 每次比较取出最小的那个节点，然后连起来。不要想着修改指针连起来。
    // 不好的思路 不经典
    // 参考https://leetcode.cn/problems/merge-two-sorted-lists/submissions/499948831/?envType=study-plan-v2&envId=top-100-liked
    func mergeTwoLists(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
        if l1 == nil {
            return l2
        } else if (l2 == nil) {
            return l1
        }
        var node: ListNode? = nil
        if l1!.val <= l2!.val {
            node = l1
            node?.next = mergeTwoLists(l1?.next, l2)
        } else {
            node = l2
            node?.next = mergeTwoLists(l1, l2?.next)
        }
        return node
    }
    
    //MARK: -25、树的子结构
    //(约定空树不是任意一个树的子结构)
    func isSubStructure(_ A: TreeNode?, _ B: TreeNode?) -> Bool {
        var isSub = false
        if A != nil && B != nil {//避免空树
            if A?.val == B?.val  {//根节点相等，不判断也行
                isSub = subTreeDfs(A, B)
            }
            if !isSub {
                isSub = isSubStructure(A?.left, B) || isSubStructure(A?.right, B)
            }
        }
        return isSub
    }
    
    func subTreeDfs(_ A: TreeNode?, _ B: TreeNode?) -> Bool {
        if B == nil {
            return true
        } else if (A == nil) {
            return false
        }
        if A?.val != B?.val {
            return false
        }
        let subEuqal = subTreeDfs(A?.left, B?.left) && subTreeDfs(A?.right, B?.right)
        
        return subEuqal
    }
    
    
    //MARK: -29、顺时针打印矩阵？待做
    func spiralOrder(_ matrix: [[Int]]) -> [Int] {
//        if matrix.isEmpty {
//            return []
//        } else if matrix[0].isEmpty {
//            return []
//        }
//
        //麻烦活
        
        return []
    }
    
    //MARK: -31、栈的压入、弹出序列
    func validateStackSequences(_ pushed: [Int], _ popped: [Int]) -> Bool {
        var assitArr = [Int]()//辅助栈模拟进栈出栈过程
        var i = 0//访问pop,标记pop序列是否检查结束
        var j = 0//访问push
                
        while i < popped.count {//换种写法 合成一个大循环 不要在内循环了
            let num = popped[i]
            if let element = assitArr.last, element == num {
                assitArr.removeLast()
            } else {
                let r = j
                var found = false
                
                for index in r..<pushed.count {
                    j = j + 1
                    let element = pushed[index]
                    assitArr.append(element)
                    if element == num {
                        found = true
                        assitArr.removeLast()
                        break
                    }
                }
                if !found {
                    return false
                }
            }
            i = i + 1
        }//我觉得这里不需要判断栈是不是空的，只要弹出序列检查完了就ok
        return true
    }
    
    //MARK: -42、连续子数组的最大和
    //f(i) 代表以第i 个数结尾的「连续子数组的最大和」，应该叫和 不是最大和
    func maxSubArray(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }
        var maxSum = 0
        var dp = nums[0]
        for i in 1..<nums.count {
            //如果当前值加上上一个dp<自身 就取自身，否则就加上，后面有更大的可能
            dp = max(dp + nums[i], nums[i])
            maxSum = max(maxSum, dp)//要得到的是最大值，关键是看明白题目意思，然后考虑动态规划
        }
        
        return maxSum
    }
    
    //MARK:  -58 翻转单词顺序
    func reverseWords(_ s: String) -> String {
        let arr = String(s.reversed()).components(separatedBy: CharacterSet.whitespaces)
        var wordsArr = Array<String>()
        for word in arr {
            if word.count > 0 {
                wordsArr.append(String(word.reversed()))
            }
        }
        let s = wordsArr.joined(separator: " ")
        return s
    }
    //左旋字符串  abc1234  1234abc
    //翻转3次 前半部分一次 后半部分一次  整体一次
    func reverseLeftWords(_ s: String, _ n: Int) -> String {
        
        if s.count < n, n < 1 {
            return s
        }
        //什么傻逼操作
        let r = s.startIndex..<s.index(s.startIndex, offsetBy: 3)
        _ = String(s[r])
        
        let halfs = s.substring(to: s.index(s.startIndex, offsetBy: n))
        let behind = s.substring(from: s.index(after: s.index(s.startIndex, offsetBy: n - 1)))
        let newStr = String(halfs.reversed()) + String(behind.reversed())
        return String(newStr.reversed())
    }
    
    // MARK:  -60 n个筛子的点数
    /*
     n个筛子和最小是n最大是6n
     和的范围是 6n - n + 1
     */
    //先用递归做 这tm是中等题目吗
//    func dicesProbability(_ n: Int) -> [Double] {
//
//
//    }
    // MARK:  -61 扑克牌中的顺子
    func isStraight(_ nums: [Int]) -> Bool {
        let newNums = nums.sorted { a, b in
            return a < b
        }
        var zeroCount = 0
        for num in newNums {
            if num == 0 {
                zeroCount += 1
            }
        }
        var gapCount = 0
        var index1 = zeroCount//记录下标开始比较相邻数字差的个数
        var index2 = zeroCount + 1
        while index2 < newNums.count {
            if newNums[index1] == newNums[index2] {
                return false//两个数相等
            }
            //2 和 5 差是3 中间隔2个空格
            gapCount = gapCount + (newNums[index2] - newNums[index1] - 1)
            index1 = index2
            index2 += 1
        }
        if gapCount <= zeroCount {
            return true
        }
        
        return false
    }
    
    
    //MARK:  - 64 1+2+...+n
    //不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）
    func sumNums(_ n: Int) -> Int {
        //不能使用循环只能用递归 但是这个判断也不行
//        return n == 0 ? 0 : (n + sumNums1(n - 1))
        //用逻辑运算的短路性质
        //swift不能这样用  &&两边不能是 非bool 😅
//        (n == 0) && sum = sum + sumNums(n-1)
        var sum = n
        (n > 0) && {
            sum = sum + sumNums(n-1)
            return true
        }()
        return sum
    }
    
    func sumNumsAssi(_ n: Int) -> Int {
        return n + sumNums(n - 1)
    }
}


//**************************************************************

//和树相关的
class TreeSolution {
    //MARK: -27、二叉树的镜像
    //这个题要把空考虑进去 输入 1 输出 1 ，输入1 2 输出 1 null 2
    func mirrorTree(_ root: TreeNode?) -> TreeNode? {
        guard let root = root else {
            return nil
        }
        //空不考虑
//        guard (root.left != nil), (root.right != nil) else {
//            return root
//        }
        let tempNode = root.left
        root.left = root.right
        root.right = tempNode
        
        _ = mirrorTree(root.left)
        _ = mirrorTree(root.right)
        return root
    }
    
    //MARK: -28、对称的二叉树
    //和上一个题不同，这个对称以自身根节点来说的
    func isSymmetric(_ root: TreeNode?) -> Bool {
        //子树null考虑进去，对一棵树的前序遍历和 另一种遍历一一比较
        //另一种遍历方式是  根右左
        return isSymmetricDfs(root, root)
    }
    func isSymmetricDfs(_ root1: TreeNode?, _ root2: TreeNode?) -> Bool {
        if root1 == nil && root2 == nil {
            return true
        } else if (root1 == nil || root2 == nil) {
            return false
        }
        var same = false
        if root1?.val == root2?.val {
            //遍历的变体
            same = isSymmetricDfs(root1?.left, root2?.right) && isSymmetricDfs(root1?.right, root2?.left)
        }
        return same
    }
    
    //MARK: -32、从上到下打印二叉树
    //层序遍历
    func levelOrder(_ root: TreeNode?) -> [Int] {
        var queue = Array<TreeNode>()
        var values = Array<Int>()
        
        if let root = root {
            queue.append(root)
            while !queue.isEmpty {
                let node = queue.removeFirst()
                values.append(node.val)
                if let left = node.left {
                    queue.append(left)
                }
                if let right = node.right {
                    queue.append(right)
                }
            }
        }
        return values
    }
    //每层打印一行
    func levelOrder2(_ root: TreeNode?) -> [[Int]] {
        var queue = Array<TreeNode>()
        var values = Array<Array<Int>>()
        
        if let root = root {
            queue.append(root)//丢入根节点
            var currentNodeNum = 1//记录当前第一层总节点数
            var nextLevelNum = 0//记录下一层节点数
            var arr = [Int]()
            while !queue.isEmpty {
                let node = queue.removeFirst()
                arr.append(node.val)
                if let left = node.left {
                    queue.append(left)
                    nextLevelNum += 1
                }
                if let right = node.right {
                    queue.append(right)
                    nextLevelNum += 1
                }
                currentNodeNum -= 1//访问完就减一次
                if currentNodeNum == 0 {
                    currentNodeNum = nextLevelNum
                    nextLevelNum = 0
                    values.append(arr)
                    arr.removeAll()
                }
            }
        }
        return values
    }
    //之字形打印
    func levelOrder3(_ root: TreeNode?) -> [[Int]] {
        //第1层 左到右 2层右到左
        var oddQueue = Array<TreeNode>()//模拟栈,奇数层 左往右
        var evenQueue = Array<TreeNode>()
        var values = Array<Array<Int>>()
        if let root = root {
            oddQueue.append(root)
            var currentNodeNum = 1//记录当前第一层总节点数
            var nextLevelNum = 0//记录下一层节点数
            var currentFloor = 1//当前哪一层
            var arr = [Int]()
            while !oddQueue.isEmpty || !evenQueue.isEmpty {
                
                if currentFloor & 1 == 1 {//当前奇数
                    let node = oddQueue.removeLast()
                    arr.append(node.val)
                    if let leftNode = node.left {
                        evenQueue.append(leftNode)
                        nextLevelNum += 1
                    }
                    if let rightNode = node.right {
                        evenQueue.append(rightNode)
                        nextLevelNum += 1
                    }
                } else {//当前打印偶数层
                    let node = evenQueue.removeLast()
                    arr.append(node.val)
                    if let rightNode = node.right {
                        oddQueue.append(rightNode)
                        nextLevelNum += 1
                    }
                    if let leftNode = node.left {
                        oddQueue.append(leftNode)
                        nextLevelNum += 1
                    }
                }
                currentNodeNum -= 1
                if currentNodeNum == 0 {//下一次遍历节点准备
                    currentFloor += 1
                    currentNodeNum = nextLevelNum
                    nextLevelNum = 0
                    values.append(arr)
                    arr.removeAll()
                }
                
            }
        }
        
        return values
    }
    
    //MARK: -33、二叉搜索树的后续遍历序列
    //左子树中所有节点的值< 根节点的值；右子树中所有节点的值> 根节点的值；其左、右子树也分别为二叉搜索树
    func verifyPostorder(_ postorder: [Int]) -> Bool {
        guard postorder.count > 0 else {return true}
        let length = postorder.count
        let rootVal = (postorder.last)!
        var leftTree = [Int]()
        var rightTree = [Int]()
        
        var leftRootIndex = 0//左子树中根节点的下标
        for (index, value) in postorder.enumerated() {
            if value < rootVal {
                leftTree.append(value)
            } else {
                leftRootIndex = index - 1//有可能为-1,考虑全
                break
            }
        }
        
        //有可能为-1,考虑全 没有左子树的情况
        if leftRootIndex < length {
            for i in (leftRootIndex + 1)..<length - 1 {
                let val = postorder[i]
                if val > rootVal {
                    rightTree.append(val)
                } else {
                    return false
                }
            }
        }
        var leftOk = true
        if !leftTree.isEmpty {
            leftOk = verifyPostorder(leftTree)
        }
        
        var rightOk = true
        if !rightTree.isEmpty {
            rightOk = verifyPostorder(rightTree)
        }
        return leftOk && rightOk
    }
    
    //MARK: -34、二叉树中和为某一值的路径
    //letcode上树的数组标识 不太合适的
    //[5,4,8,11,null,13,4,7,2,null,null,5,1]  这里应该是[5,4,8,11,-1,13,4,7,2,-1,-1,-1,-1,5,1] 个数组创建
    var paths = Array<[Int]>()
    var nodeArr = Array<Int>()
    var sum = 0
    func pathSum(_ root: TreeNode?, _ target: Int) -> [[Int]] {
        guard let root = root else {
            return Array<[Int]>()
        }
        pathSumDfs(root, target)
        return paths
    }
    
    func pathSumDfs(_ root: TreeNode?, _ target: Int) {
        guard let root = root else {
            return
        }
        self.sum = self.sum + root.val
        nodeArr.append(root.val)
        if root.left == nil && root.right == nil {
            if sum == target {
                paths.append(nodeArr)
            }
        }
        if root.left != nil {
            pathSumDfs(root.left, target)
        }
        if root.right != nil {
            pathSumDfs(root.right, target)
        }
        //这里是递归结束回到当前节点！！！
        self.sum = self.sum - root.val
        nodeArr.removeLast()
    }
    
    //MARK: -55 二叉树的深度
    func maxDepth(_ root: TreeNode?) -> Int {
            guard let root = root else { return 0 }
        //2、初始化队列，直接加入根节点，作为第一层开始循环
        var queue = [root]
        var res = 0
        
        while queue.isEmpty == false {
            var list = [TreeNode]()
            for node in queue {
                if let left = node.left {
                    list.append(left)
                }
                if let right = node.right {
                    list.append(right)
                }
            }
            queue = list
            //访问完一次queue深度加1
            res += 1
        }
        return res
        }
    
    //MARK: -68 二叉树的最近公共祖先
    //还是要画图理解，要么root两边的 要么单边 单边就是找到和root相等的其中一个
    //数据范围从1开始
    func lowestCommonAncestor ( _ root: TreeNode?,  _ o1: Int,  _ o2: Int) -> Int {
        guard let root = root else { return 0 }
        if root.val == o1 || root.val == o2 {
            return root.val
        }
        let leftV = lowestCommonAncestor(root.left, o1, o2)
        let rightV = lowestCommonAncestor(root.right, o1, o2)
        if leftV == 0 {
            return rightV
        }
        if rightV == 0 {
            return leftV
        }
        return root.val
    }
    //MARK:  - 58二叉搜索树的公共祖先
    func lowestCommonAncestor1 ( _ root: TreeNode?,  _ p: Int,  _ q: Int) -> Int {
        var root = root
        while root != nil {
            if let node = root {
                if node.val > p && node.val > q {
                    root = root?.left
                } else if node.val < p && node.val < q {
                    root = root?.right
                } else {
                    break
                }
            }
        }
        return root?.val ?? 0
    }
    
}
 
//MARK: -09用两个栈实现队列
class CQueue {
    //数组做栈，入栈append,出栈removelast
    var stack1 = [Int]()//入队时放入stack1
    var stack2 = [Int]()//需要出队的
    //算法如此，从代码上来看，一个数组就能实现。毕竟oc和swift都没有栈，只有数组和可用的api啦
    init() {

    }
    
    func appendTail(_ value: Int) {
        stack1.append(value)
    }
    
    func deleteHead() -> Int {
        var value = -1
        if stack2.isEmpty {
            while !stack1.isEmpty {
                stack2.append(stack1.removeLast())
            }
        }
        
        if !stack2.isEmpty {
            value = stack2.removeLast()
        }
        return value
    }
}
 

//MARK: -30、包含min函数的栈
class MinStack {

    var dataArray: [Int]
    var assitArray: [Int]
    var minValue: Int
    init() {
        self.dataArray = [Int]()
        self.assitArray = [Int]()
        self.minValue = 0
    }
    
    func push(_ x: Int) {
        if self.dataArray.isEmpty {
            //由于不能为nil，最小值不知道改设置成多少，所以应该以第一次输入为准
            self.minValue = x
        }
        self.dataArray.append(x)
        self.minValue = Swift.min(self.minValue, x)
        self.assitArray.append(self.minValue)
    }
    
    func pop() {
        self.dataArray.removeLast()
        self.assitArray.removeLast()
        //更新最小值
        if let minNumber = self.assitArray.last {
            self.minValue = minNumber
        }
    }
    
    func top() -> Int {
        if let lastNumber = self.dataArray.last {
          return lastNumber
        }
        return 0
    }
    
    func min() -> Int {
        return self.minValue
    }
}

